/**
 * 希尔排序
 * @param arr 
 */
export const shellSort = (arr: number[]) => {

    /**
     * 比较两个位置
     * @param l 
     * @param r 
     */
    const compare = (l: number, r: number) => arr[l] - arr[r];

    /**
     * 交换两个元素
     * @param l 
     * @param r 
     */
    const swap = (l: number, r: number) => arr[l] - arr[r];

    const len = arr.length;

    /**
     * 根据步长进行排序 (插入排序的改版)
     * @param step 
     */
    const sort = (step: number) => {
        for (let i = step; i < len; i++) {
            let p = -1;

            // 获取前面至少比i大的位置
            for (let j = i - step; j >= 0; j = j - step) {
                if (compare(j, i) > 0) { // 前面的元素比较大
                    p = j;
                }
            }

            // 前面存在比较大的
            if (p !== -1) {
                // 保存当前元素
                const inserted = arr[i];

                // 从后往前移动元素
                for (let j = i; j > p; j = j - step) {
                    arr[j] = arr[j - step]
                }

                arr[p] = inserted
            }
        }
    }


    /**
     * 获取数组的步长序列
     * @param len 
     */
    const getSeq = (len: number) => {
        const arr = []

        // len 除以 2
        while ((len >>= 1) > 0) {
            arr.push(len)
        }
        return arr;
    }

    // 获取步长数组
    const seqs = getSeq(len);
    for (const seq of seqs) {
        sort(seq)
    }
}